import java.util.*;

public class StandardTraverse {
    public int findCircleNum(int[][] isConnected) {
        int cities = isConnected.length;
        boolean[] visited = new boolean[cities];
        int provinces = 0;

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < cities; i++) {
            if (!visited[i]) {
                queue.offer(i);
                while (!queue.isEmpty()) {
                    int cur = queue.poll();
                    visited[cur] = true;
                    for (int j = 0; j < cities; j++) {
                        if (isConnected[cur][j] == 1 && !visited[j]) {
                            queue.offer(j);
                        }
                    }
                }
                provinces++;
            }
        }
        return provinces;
    }



    public List<Integer> eventualSafeNodes(int[][] graph) {
        int n = graph.length;
        int[] color = new int[n];

        class InnerClass {
            public static boolean isSafe(int x, int[] color, int[][] graph) {
                if (color[x] > 0) {
                    return color[x] == 2;
                }
                color[x] = 1;

                for (int y : graph[x]) {
                    if (!isSafe(y, color, graph)) {
                        return false;
                    }
                }

                color[x] = 2;
                return true;
            }
        }

        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (InnerClass.isSafe(i, color, graph)) {
                ans.add(i);
            }
        }
        return ans;

    }


    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        int n = rooms.size();

        class Inner {
            private boolean[] visited;
            private int nums;

            public Inner(int n) {
                this.visited = new boolean[n];
                this.nums = 0;
            }

            public void dfs(int x) {
                this.visited[x] = true;
                this.nums++;

                for (int y : rooms.get(x)) {
                    if (!this.visited[y]) {
                        this.dfs(y);
                    }
                }
            }
        }
        Inner inner = new Inner(n);
        inner.dfs(0);
        return inner.nums == n;
    }


    public int[] shortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {
        List<Integer>[][] next = new List[2][n];
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < n; j++) {
                next[i][j] = new ArrayList<>();
            }
        }

        for (int[] edge : redEdges) {
            next[0][edge[0]].add(edge[1]);
        }
        for (int[] edge : blueEdges) {
            next[1][edge[0]].add(edge[1]);
        }

        int[][] dist = new int[2][n];
        Arrays.fill(dist[0], Integer.MAX_VALUE);
        Arrays.fill(dist[1], Integer.MAX_VALUE);
        dist[0][0] = 0;
        dist[1][0] = 0;
        Queue<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[]{0, 0});
        queue.offer(new int[]{1, 0});

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            for (int y : next[1 - cur[0]][cur[1]]) {
                if (dist[1 - cur[0]][y] != Integer.MAX_VALUE) {
                    continue;
                }
                dist[1 - cur[0]][y] = dist[cur[0]][cur[1]] + 1;
                queue.offer(new int[]{1 - cur[0], y});
            }
        }

        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            ans[i] = Math.min(dist[0][i], dist[1][i]);
            if (ans[i] == Integer.MAX_VALUE) {
                ans[i] = -1;
            }
        }
        return ans;
    }



    public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {
        int res = 0;

        class Inner {
            private int headId;
            private int[] manager;
            private int[] informTime;
            private Map<Integer, Integer> memory;

            public Inner(int headId, int[] manager, int[] informTime, int n) {
                this.headId = headId;
                this.manager = manager;
                this.informTime = informTime;
                memory = new HashMap<>(n);
            }

            public int dfs(int cur) {
                if (cur == headID)
                    return 0;

                if (!memory.containsKey(cur)) {
                    memory.put(cur, dfs(manager[cur]) + informTime[manager[cur]]);
                }
                return memory.get(cur);
            }
        }
        Inner inner = new Inner(headID, manager, informTime, n);

        for (int i = 0; i < n; i++) {
            res = Math.max(res, inner.dfs(i));
        }
        return res;
    }



    public int minReorder(int n, int[][] connections) {
        List<List<int[]>> graph = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int[] edge : connections) {
            graph.get(edge[0]).add(new int[]{edge[1], 1});
            graph.get(edge[1]).add(new int[]{edge[0], 0});
        }

        class Inner {
            private List<List<int[]>> graph;

            public Inner(List<List<int[]>> graph) {
                this.graph = graph;
            }

            public int dfs(int cur, int parent) {
                int res = 0;
                for (int[] edge : graph.get(cur)) {
                    if (edge[0] == parent) {
                        continue;
                    }
                    res += edge[1] + dfs(edge[0], cur);
                }
                return res;
            }
        }

        Inner inner = new Inner(graph);
        return inner.dfs(0, -1);
    }



    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        class Inner {
            private List<List<Integer>> paths;
            private Deque<Integer> stack;
            private int target;

            public Inner(int n) {
                this.paths = new ArrayList<>();
                this.stack = new ArrayDeque<>();
                this.stack.addLast(0);
                this.target = n - 1;
            }

            public void dfs(int x, int[][] graph) {
                if (x == this.target) {
                    this.paths.add(new ArrayList<>(this.stack));
                    return;
                }
                for (Integer y : graph[x]) {
                    this.stack.addLast(y);
                    dfs(y, graph);
                    this.stack.removeLast();
                }
            }
        }

        Inner inner = new Inner(graph.length);
        inner.dfs(0, graph);
        return inner.paths;
    }


    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
        List<List<Integer>> graph = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        for (List<Integer> edge : connections) {
            graph.get(edge.get(0)).add(edge.get(1));
            graph.get(edge.get(1)).add(edge.get(0));
        }

        class Tarjan {
            private List<List<Integer>> graph;
            private int[] low;
            private int[] time;
            private int idx;
            private List<List<Integer>> ans = new ArrayList<>();

            public Tarjan(List<List<Integer>> graph, int n) {
                this.graph = graph;
                this.low = new int[n];
                this.time = new int[n];
                this.idx = 0;
            }

            public void dfs(int cur, int parent) {
                this.low[cur] = this.time[cur] = ++this.idx;

                for (int child : graph.get(cur)) {
                    if (this.time[child] == 0) {
                        this.dfs(child, cur);
                        this.low[cur] = Math.min(this.low[cur], low[child]);
                        if (this.low[child] > this.time[cur])
                            ans.add(Arrays.asList(cur, child));
                    } else if (this.time[child] < this.time[cur] && child != parent)
                        this.low[cur] = Math.min(this.low[cur], this.time[child]);
                }
            }
        }

        Tarjan tarjan = new Tarjan(graph, n);
        tarjan.dfs(0, -1);
        return tarjan.ans;
    }

    public static void main(String[] args) {
        List<List<Integer>> graph = new ArrayList<>();
        graph.add(Arrays.asList(0, 1));
        graph.add(Arrays.asList(1, 2));
        graph.add(Arrays.asList(2, 0));
        graph.add(Arrays.asList(1, 3));

        StandardTraverse solution = new StandardTraverse();
        solution.criticalConnections(4, graph);
    }

}
